#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#include<iostream>
#include<fstream>
#include<sstream>
#include<vector>
#include<random>

using namespace std;
 
int NETWORK_SIZE = 10;        // 网络总节点数
int M = 2;          // 保证平均度4
int M_0 = 2;        // 网络初始节点数

struct Node;
typedef struct Node* NodePtr;
typedef struct Node {
	int degree;
	double weight;
	double probabilityDistribution;
}Node;
 
Node* decisionMaking;
int** adjacentMatrix;
int* initalNetwork;
 
void initial()
{
	if (!(decisionMaking = (NodePtr)malloc(sizeof(Node) * (NETWORK_SIZE + 1))))
	{
		printf("decisionMaking* malloc error\n");
		exit(0);
	}
	if (!(adjacentMatrix = (int**)malloc(sizeof(int*) * (NETWORK_SIZE + 1))))
	{
		printf("adjacentMatrix** malloc error\n");
		exit(0);
	}
	int i;
	for (i = 1; i <= NETWORK_SIZE; i++)
	{
		if (!(adjacentMatrix[i] = (int*)malloc(sizeof(int) * (NETWORK_SIZE + 1))))
		{
			printf("adjacentMatrix[%d]* malloc error\n", i);
			exit(0);
		}
	}
	if (!(initalNetwork = (int*)malloc(sizeof(int) * (M_0 + 1))))
	{
		printf("initalNetwork* malloc error\n");
		exit(0);
	}
}

/*
 * 通过adjacentMatrix更新decisionMaking数组
 * */
void updateDecisionMakingData() {
	int i, j, totalDegree = 0;
 
	for (i = 1; i <= NETWORK_SIZE; i++)
		decisionMaking[i].degree = 0;
	for (i = 1; i <= NETWORK_SIZE; i++)
		for (j = 1; j <= NETWORK_SIZE; j++)
			decisionMaking[i].degree += adjacentMatrix[i][j];
	for (i = 1; i <= NETWORK_SIZE; i++)
		totalDegree += decisionMaking[i].degree;
	for (i = 1; i <= NETWORK_SIZE; i++)
		decisionMaking[i].weight = decisionMaking[i].degree / (double)totalDegree;
	decisionMaking[1].probabilityDistribution = decisionMaking[1].weight;
	for (i = 2; i <= NETWORK_SIZE; i++)
		decisionMaking[i].probabilityDistribution = decisionMaking[i - 1].probabilityDistribution + decisionMaking[i].weight;
}

/*
 * 初始化：在NETWORK_SIZE中随机选择M_0个节点构成连通的网络。
 * */
void initalNetwork_M0_connected() {
	int i, j, randomFirst, randomSecond;
	for (i = 1; i <= NETWORK_SIZE; i++)
		for (j = 1; j <= NETWORK_SIZE; j++)
			adjacentMatrix[i][j] = 0;
	// 随机产生M_0个节点
	for (i = 1; i <= M_0; i++)
	{
		initalNetwork[i] = rand() % NETWORK_SIZE + 1;
		for (j = 1; j < i; j++)
			if (initalNetwork[i] == initalNetwork[j])
			{
				i--;
				break;
			}
	}
	for (i = 1; i < M_0; i++)
		adjacentMatrix[initalNetwork[i]][initalNetwork[i + 1]] = adjacentMatrix[initalNetwork[i + 1]][initalNetwork[i]] = 1;
	adjacentMatrix[initalNetwork[M_0]][initalNetwork[1]] = adjacentMatrix[initalNetwork[1]][initalNetwork[M_0]] = 1;
 
	//showAdjacentMatrix();
	updateDecisionMakingData();
}
 
/*
 * 构造BA无标度网络模型
 * */
void generateFreeScaleNetwork() {
	int i, k, j = 1, length = 0;
	int *const random_auxiliary_old = (int*)malloc(sizeof(int)*(NETWORK_SIZE + 1));
	int *const random_auxiliary = (int*)malloc(sizeof(int)*(NETWORK_SIZE + 1 - M_0));
 
	/*
	 * 要保证每次引入一个<新的>的节点，所以要随机选择不重复的节点加入，并且把初始网络中的M_0个节点先删除
	 * */
	for (i = 1; i <= NETWORK_SIZE; i++)
		random_auxiliary_old[i] = i;
 
	for (i = 1; i <= M_0; i++)
		random_auxiliary_old[initalNetwork[i]] = 0;
	for (i = 1; i <= NETWORK_SIZE; i++)
		if (random_auxiliary_old[i] != 0)
			random_auxiliary[j++] = random_auxiliary_old[i];
 
	/*
	 * 添加新的节点构造无标度网络
	 * */
	int new_node_index, new_node_value;
	double random_decision = 0.0;
	int targetNode;					//表示找到的已经在网络中的将要连接的节点
	length = NETWORK_SIZE - M_0;
	int flag;
	for (i = 1; i <= NETWORK_SIZE - M_0; i++)
	{
		new_node_index = rand() % length + 1;
		new_node_value = random_auxiliary[new_node_index];
		random_auxiliary[new_node_index] = random_auxiliary[length--];
		for (j = 1; j <= M; j++)		//根据概率连接到已存在网络中的M个节点，不可以重边，不可以自连。
		{
			flag = 0;
			random_decision = (rand() % 1000) / (double)1000;
			for (k = 1; k <= NETWORK_SIZE; k++)
			{
				// 从第一个节点到最后一个节点比较probabilityDistribution和random_desction的大小，
				// 由于probabilityDistribution是有序的，所以可以使用一些高级的算法来提高查找的效率.
				if (decisionMaking[k].probabilityDistribution >= random_decision && decisionMaking[k].degree != 0 && adjacentMatrix[new_node_value][k] != 1)
				{
					/*
					 *
					 *  如何按照可能性大小来选择要连哪一个点：
					 *         选择的已经在网络中的点是：随机产生的0-1之间的概率p，找这样的点：
					 *         它的累加概率（probabilityDistribution）是大于p的最小的值所对应的点。
					 *
					 */
					targetNode = k;
					flag = 1;
					break;
				}
			}
			if (flag == 0)
				/*
				 * 之前少考虑了这种情况，因为总要选择一个网络中的点接入。但是当产生了比较大的随机概率p，可能
				 * 在他后面（按probabilityDistribution来说）没有可选的点（要么选择过了，要么不在网络中），则重新开始
				 */
			{
				for (k = 1; k <= NETWORK_SIZE; k++)
				{
					if (decisionMaking[k].degree != 0 && adjacentMatrix[new_node_value][k] != 1)
					{
						targetNode = k;
						break;
					}
				}
			}
			//printf(" target node is %d\n", targetNode);
			adjacentMatrix[new_node_value][targetNode] = adjacentMatrix[targetNode][new_node_value] = 1;
		}
		updateDecisionMakingData();		//else新选的加入节点和已有网络中的M个边都链接后再更新
	}
}
 
void write2File_degreedistribut(double* statistic)
{
	FILE* fwrite;
	if (NULL == (fwrite = fopen("d:\\project\\freeScale_degree.txt", "w")))
	{
		cout << "open file error" << endl;
		exit(0);
	}
	int i;
	for (i = 0; i < NETWORK_SIZE; i++)
		fprintf(fwrite, "%d %f\n", i, statistic[i]);//i表示度，statistic[i]为其概率
	fclose(fwrite);
}
 
 //计算度分布，并调用write2File_degreedistribut函数将度分布写入文件freeScale_degree.txt中
void calculateDegreeDistribution()
{
	int* degree;
	double* statistic;
	int i, j;
	double averageDegree = 0.0;
	if (!(degree = (int*)malloc(sizeof(int) * (NETWORK_SIZE + 1))))
	{
		cout << "degree*malloc error" << endl;
		exit(0);
	}
	for (i = 1; i <= NETWORK_SIZE; i++)degree[i] = 0;
	if (!(statistic = (double*)malloc(sizeof(double) * NETWORK_SIZE)))
	{
		cout << "statistic*malloc error" << endl;
		exit(0);
	}
	for (i = 0; i < NETWORK_SIZE; i++)statistic[i] = 0.0;
	for (i = 1; i <= NETWORK_SIZE; i++)
		for (j = 1; j <= NETWORK_SIZE; j++)
			degree[i] = degree[i] + adjacentMatrix[i][j];
	for (i = 1; i <= NETWORK_SIZE; i++)
		averageDegree += degree[i];
	for (i = 1; i <= NETWORK_SIZE; i++)
		statistic[degree[i]]++;
	double indentify = 0.0;
	for (i = 0; i < NETWORK_SIZE; i++)
	{
		statistic[i] = statistic[i] / (double)NETWORK_SIZE;
		indentify += statistic[i];
	}
	write2File_degreedistribut(statistic);
}
 
//将BA网络的邻接矩阵写入文件freeScale.txt
void writeDataToFile()
 {
	FILE* fout;
	if (NULL == (fout = fopen("d:\\project\\freeScale.txt", "w")))
	{
		//printf("open file error!\n");
        cout << "open file error" << endl;
		exit(0);
	}
	int i;
	int j;
	for (i = 1; i <= NETWORK_SIZE; i++)
	{
		for (j = 1; j <= NETWORK_SIZE; j++) {
			fprintf(fout, "%d ", adjacentMatrix[i][j]);
		}
		fprintf(fout, "\n");
	}
	fclose(fout);
}

int main(int argc, char** argv) {
    initial();
	initalNetwork_M0_connected();
	generateFreeScaleNetwork();
	writeDataToFile();
	calculateDegreeDistribution();
    system("pause");
    return 0;
}